class Solution {
public:
    string str[10] = {"",    "",    "abc",  "def", "ghi",
                      "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> v;
    void dfs(int pos, string&& s, const string& digits) {
        if (pos == digits.size()) {
            v.push_back(s);
            return;
        }
        string it = str[digits[pos] - '0'];
        for (int i = 0; i < it.size(); i++) {
            s.push_back(it[i]);
            dfs(pos + 1, move(s), digits);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        dfs(0, string(), digits);
        return v;
    }
};